package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Code90 {
	
	public void dfs(int start,int n,int[] nums,boolean[] vis,Stack<Integer> sck,List<List<Integer>> result){
		result.add(new ArrayList<Integer>(sck));
		
		for(int i=start;i<n;i++){
			if(vis[i] || (i>0 && nums[i]==nums[i-1] && !vis[i-1]) || (!sck.isEmpty() && nums[i]<sck.peek()))
				continue ;
			sck.push(nums[i]);
			vis[i]=true;
			dfs(start+1,n,nums,vis,sck,result);
			vis[i]=false;
			sck.pop();
		}
	}
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		 List<List<Integer>> result=new ArrayList<List<Integer>>();
	        int n=nums.length;
	        if(n==0)
	        	return result;
	        int max=(1<<n);
	        Arrays.sort(nums);
		 dfs(0,n,nums,new boolean[n],new Stack<Integer>(),result);
		 return result;
	}
	
    public List<List<Integer>> subsetsWithDupII(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Set<List<Integer>> set=new HashSet<List<Integer>>();
        
        int n=nums.length;
        if(n==0)
        	return result;
        int max=(1<<n);
        Arrays.sort(nums);
        
        for(int i=0;i<max;i++){
        	List<Integer> list=new ArrayList<Integer>();
        	for(int j=0;j<n;j++){
        		if((i&(1<<j))>0){
        			list.add(nums[j]);
        		}
        	}
        	if(set.contains(list))
        		continue;
        	set.add(list);
        	result.add(list);
        }
        return result;
    }
    public static void main(String[] args){
    	int[] A={1,2,3};
    	Code90 code=new Code90();
    	code.subsetsWithDup(A);
    }
}
